Chapter 7 Permutations and Combinations (Concepts)

Fundamental Principle of Counting

Permutations and Combinations are mathematical concepts that deal with counting possible arrangements and selections of objects from a set. The foundation of these topics lies in the basic rules of counting, collectively known as the Fundamental Principle of Counting (FPC).

The FPC helps us determine the total number of outcomes for a complex event by breaking it down into simpler events or decisions. It consists of two main principles: the Multiplication Principle and the Addition Principle.

Multiplication Principle

The Multiplication Principle applies when a task is performed in a sequence of stages or steps. It is used to find the total number of outcomes when events happen one after another (using the keyword "AND").

Principle: If a first task can be performed in $n_1$ ways, and a second task can be performed in $n_2$ ways, then the total number of ways to perform the first task AND the second task is the product:

Examples of the Multiplication Principle

Example A: Creating an Outfit

A person has 3 different shirts and 4 different pairs of pants. How many different outfits can they create?

To create an outfit, the person must choose a shirt AND choose a pair of pants.

• Number of ways to choose a shirt = 3.
• Number of ways to choose pants = 4.

By the Multiplication Principle, the total number of outfits is:

Example B: Forming a Code (Without Repetition)

How many 4-letter codes can be formed using the first 10 letters of the alphabet if no letter can be repeated?

We have four positions to fill:

• 1st position: 10 choices.
• 2nd position: 9 choices (one letter is used).
• 3rd position: 8 choices (two letters are used).
• 4th position: 7 choices (three letters are used).

Total codes = $10 \times 9 \times 8 \times 7 = 5040$.

Example C: Forming a Number (With Repetition)

How many 3-digit numbers can be formed using the digits 0, 1, 2, 3, 4, 5 if repetition is allowed?

We have three positions to fill: Hundreds, Tens, and Units.

• Hundreds place: 5 choices (cannot be 0).
• Tens place: 6 choices (0 is now allowed, repetition is okay).
• Units place: 6 choices.

Total 3-digit numbers = $5 \times 6 \times 6 = 180$.

Addition Principle

The Addition Principle applies when we have a choice between two or more mutually exclusive options. It is used to find the total number of outcomes when we can do one task OR another (using the keyword "OR").

Principle: If a task can be performed in $n_1$ ways, and another, mutually exclusive task can be performed in $n_2$ ways, then the total number of ways to perform either the first task OR the second task is the sum:

Examples of the Addition Principle

Example D: Choosing a Class Representative

A class has 15 boys and 12 girls. In how many ways can one student be selected as a representative?

The representative can be a boy OR a girl. These two choices are mutually exclusive.

• Number of ways to choose a boy = 15.
• Number of ways to choose a girl = 12.

By the Addition Principle, the total number of ways to choose a representative is:

Example E: Choosing a Mode of Transport

A person can travel from city A to city B by one of 3 buses or by one of 2 trains. In how many ways can they travel from A to B?

The person can travel by bus OR by train. The choices are mutually exclusive.

• Number of ways to travel by bus = 3.
• Number of ways to travel by train = 2.

Total ways = $3 + 2 = 5$.

Combining the Principles

Many counting problems require using both principles together.

Example F: Choosing a President and Vice-President

From a group of 6 boys and 8 girls, a President and a Vice-President are to be selected such that one is a boy and the other is a girl.

This problem has two mutually exclusive cases (Addition Principle), and each case involves a sequence of choices (Multiplication Principle).

• Case 1: President is a Boy AND Vice-President is a Girl.

  Number of ways = (Ways to choose a boy) $\times$ (Ways to choose a girl) = $6 \times 8 = 48$.

• Case 2: President is a Girl AND Vice-President is a Boy.

  Number of ways = (Ways to choose a girl) $\times$ (Ways to choose a boy) = $8 \times 6 = 48$.

The final selection can be from Case 1 OR Case 2. Since these cases are mutually exclusive, we add their outcomes:

Factorial Notation

In the realm of counting arrangements and selections, we frequently encounter the product of a sequence of decreasing positive integers. To simplify the representation of such products, we use factorial notation. This notation is fundamental to the formulas for permutations and combinations.

Definition of Factorial

For any positive integer $n$, the factorial of $n$, denoted by $n!$ (read as "n factorial"), is defined as the product of all positive integers from 1 up to $n$.

Let's calculate the factorials for the first few positive integers:

Recursive Relation

From the definition of $n!$, we can see a relationship between the factorial of $n$ and the factorial of $n-1$.

This gives us the very useful recursive relation:

This relation allows us to break down larger factorials, which is key to simplifying expressions. For example, $10! = 10 \times 9!$.

Factorial of Zero

The definition of factorial applies to positive integers. To make the recursive relation $n! = n \times (n-1)!$ consistent for the case when $n=1$, we need to define a value for $0!$.

Let's use the recursive formula with $n=1$:

Since we know that $1! = 1$, the equation becomes:

For this to be true, $0!$ must be equal to 1. Therefore, by definition:

This definition is crucial for the formulas of permutations and combinations to work correctly in all cases.

Usage and Properties

$n!$ represents the number of ways to arrange $n$ distinct objects in a sequence (a permutation of $n$ objects).

Factorial notation is defined only for non-negative integers ($0, 1, 2, 3, \dots$). It is not defined for negative integers or fractions.

Answer:

Answer:

Permutations

In combinatorics, we often need to count the number of ways to arrange objects. Permutations are arrangements where the order of the objects matters. Each unique sequence or ordering of a set of objects is called a permutation.

Definition of a Permutation

A permutation is an arrangement of a set of objects in a definite, specific order. The key idea is that changing the order creates a new, distinct permutation.

For example, consider three distinct letters: A, B, and C. If we arrange all of them, the possible permutations are:

ABC, ACB, BAC, BCA, CAB, CBA

There are 6 distinct arrangements, so there are 6 permutations of these three letters.

Often, we are interested in arranging only a smaller group of items taken from a larger set. A permutation of $n$ distinct objects taken $r$ at a time is an ordered arrangement of $r$ objects chosen from the set of $n$.

Example: Permutations vs. Combinations

Let's again use the letters A, B, and C and see the difference between permutations and combinations when we select 2 letters at a time ($n=3, r=2$).

Permutations (Order Matters):

We select 2 letters and arrange them. The possible ordered pairs are:

AB, BA, AC, CA, BC, CB

Here, AB is different from BA because the order of the letters has changed. There are 6 permutations.

Combinations (Order Does NOT Matter):

We select a group of 2 letters. The possible groups are:

{A, B}, {A, C}, {B, C}

Here, the group {A, B} is the same as the group {B, A}. We are only concerned with which letters are chosen, not their arrangement. There are 3 combinations.

Notation for Permutations

The number of permutations of $n$ distinct objects taken $r$ at a time is represented by the following standard notations:

• $P(n, r)$
• $_nP_r$
• $P_r^n$

All these symbols mean the same thing and are read as "the number of permutations of n objects taken r at a time". The conditions for this notation are:

• The $n$ objects must be distinct.
• $0 \le r \le n$.

If we try to arrange more objects than we have (i.e., if $r > n$), it's impossible. In this case, $_nP_r = 0$.

In the next section, we will derive the formula for calculating $_nP_r$ using the Fundamental Principle of Counting.

Permutations when all Objects are Different

We now use the Fundamental Principle of Counting and factorial notation to derive a formula for calculating the number of permutations when we are arranging objects from a set where all the objects are distinct. Specifically, we want to find the number of distinct ordered arrangements that can be formed by selecting $r$ objects from a set containing $n$ distinct objects.

Derivation of the Formula for $_nP_r$

Imagine we have a set of $n$ distinct objects and we want to arrange $r$ of them in a sequence. This is equivalent to filling $r$ empty slots or positions using the $n$ available objects, without repetition.

We can determine the number of options for each position sequentially:

• For the 1st position: We have $n$ distinct objects to choose from, so there are $n$ options.
• For the 2nd position: One object has been used, leaving $n-1$ objects. So there are $n-1$ options.
• For the 3rd position: Two objects have been used, leaving $n-2$ objects. So there are $n-2$ options.
• ...
• For the r-th position: We have already used $r-1$ objects, leaving $n - (r-1) = n - r + 1$ objects. So there are $n - r + 1$ options.

By the Fundamental Principle of Multiplication, the total number of ways to fill all $r$ positions is the product of the number of choices at each step:

To express this formula more compactly using factorials, we multiply and divide by $(n-r)!$:

The numerator is now the product of all integers from $n$ down to 1, which is $n!$. The denominator is $(n-r)!$. This gives us the standard formula for permutations:

This formula is valid for $0 \le r \le n$.

Arranging All $n$ Objects

A special and very common case is when we arrange all $n$ distinct objects. This means we are taking $n$ objects at a time, so $r=n$. Substituting $r=n$ into the formula:

Since we define $0! = 1$, the result is:

This means the number of ways to arrange $n$ distinct items in a row is simply $n!$.

Answer:

Answer:

Permutations when not all Objects are Distinct

In the previous section, we discussed permutations of distinct objects. However, we often encounter problems where we need to arrange objects, and some of these objects are identical. When objects are identical, swapping them among themselves does not create a new, visibly distinct arrangement. This reduces the total number of unique permutations.

Formula for Permutations with Repetition

Suppose we have a collection of $n$ objects in total. Let there be $k$ different types of objects, with $p_1$ identical objects of the first type, $p_2$ identical objects of the second type, ..., and $p_k$ identical objects of the $k$-th type. The total number of objects is $n = p_1 + p_2 + \dots + p_k$.

The number of distinct permutations (arrangements) of these $n$ objects is given by the formula:

Here, $n$ is the total number of items, and $p_1, p_2, \dots$ are the counts of each group of identical items.

Intuition behind the Formula

Let's understand why we divide. Consider the word "TEE".

If the two 'E's were distinct (say, $E_1$ and $E_2$), we would have 3 distinct objects: T, $E_1$, $E_2$. The number of arrangements would be $3! = 6$.

$T E_1 E_2$, $T E_2 E_1$, $E_1 T E_2$, $E_2 T E_1$, $E_1 E_2 T$, $E_2 E_1 T$

Now, let's make the 'E's identical again ($E_1=E_2=E$). Look at the arrangements:

• $T E_1 E_2$ and $T E_2 E_1$ both become TEE.
• $E_1 T E_2$ and $E_2 T E_1$ both become ETE.
• $E_1 E_2 T$ and $E_2 E_1 T$ both become EET.

For every unique arrangement, we have counted it $2! = 2$ times because there are $2!$ ways to arrange the two 'E's. To correct for this overcounting, we divide the initial total ($3!$) by the factorial of the count of the repeated letter ($2!$).

This same logic applies no matter how many groups of repeated objects there are. We divide by the factorial of the count for each group to eliminate the overcounting from rearranging identical items.

Answer:

Circular Permutations

Circular permutations deal with arranging objects in a circle, where rotations of the same arrangement are considered identical. For example, if 4 people (A, B, C, D) are sitting at a round table, the arrangements ABCD, BCDA, CDAB, and DABC are all the same because the relative positions of the people are unchanged.

1. Distinct Objects in a Circle:

To count unique circular arrangements, we fix the position of one object. This breaks the rotational symmetry. The remaining $n-1$ objects can then be arranged in a line in $(n-1)!$ ways.

Number of circular permutations of $n$ distinct objects = $(n-1)!$

2. Circular Permutations like Necklaces or Garlands:

In some cases, like arranging beads on a necklace, flipping the arrangement over does not create a new design. In these cases, the clockwise and anti-clockwise arrangements are considered the same. To account for this, we divide by 2.

Number of necklace/garland arrangements = $\frac{(n-1)!}{2}$

Combinations

While permutations focus on the arrangement or order of objects, combinations deal with the selection or grouping of objects where the order of selection does not matter. In many real-world scenarios, we are interested in choosing a subset of items from a larger collection without regard to the order in which they are picked.

Definition of a Combination

A combination is a selection of a set of objects from a larger group of objects, where the order of selection is not important. A combination is essentially a subset of the original set.

For example, if you have a group of three friends, A, B, and C, and you need to choose two of them to form a team, the team consisting of {A, B} is the same as the team {B, A}. The order in which you picked them does not change the final team. The distinct combinations of choosing 2 friends from 3 are:

{A, B}, {A, C}, {B, C}

There are only 3 distinct combinations.

Distinction between Permutations and Combinations

The key difference is order. To decide whether to use permutations or combinations, ask yourself: "Does the order of the items matter?"

• Permutation: Order Matters.

  Think of arranging books on a shelf, forming a phone number, or awarding gold, silver, and bronze medals in a race. Keywords: "arrange", "order", "sequence", "line up", "positions".

• Combination: Order Does NOT Matter.

  Think of choosing players for a team, picking ingredients for a salad, or selecting a committee. Keywords: "select", "choose", "form a group", "committee", "subset".

The Relationship Between Permutations and Combinations

There is a direct and logical link between permutations and combinations. We can think of forming a permutation as a two-step process:

Step 1: Choose the items (Combination). First, select a group of $r$ objects from the total $n$ objects. The number of ways to do this is the number of combinations, denoted by $_nC_r$.

Step 2: Arrange the chosen items (Permutation of the smaller group). Once you have chosen your group of $r$ objects, you can arrange them in $r!$ different ways.

By the Fundamental Principle of Multiplication, the total number of ordered arrangements ($_nP_r$) is the product of the number of ways to complete Step 1 and Step 2.

This shows that for every single combination (group of items), there are $r!$ corresponding permutations (arrangements of those items). Therefore, the number of permutations is always greater than or equal to the number of combinations (equality holds for $r=0$ or $r=1$).

This fundamental connection allows us to derive the formula for combinations from the formula for permutations.

Combinations when all Objects are Different

Having understood the distinction between permutations (order matters) and combinations (order does not matter), we now focus on deriving the formula for combinations. We consider the case where we are selecting objects from a set where all the objects are distinct.

Derivation of the Formula for $_nC_r$

In the previous section, we established the relationship between permutations and combinations:

This formula states that the number of ways to arrange $r$ items ($_nP_r$) is equal to the number of ways to first choose the group of $r$ items ($_nC_r$) and then arrange those $r$ items ($r!$).

To find the formula for $_nC_r$, we can simply rearrange this equation:

We already have the formula for permutations: $_nP_r = \frac{n!}{(n-r)!}$.

Now, we substitute this into equation (1):

Simplifying this gives the standard formula for combinations:

This formula calculates the number of ways to choose a subset of $r$ distinct objects from a larger set of $n$ distinct objects. It is valid for $0 \le r \le n$.

The notation $\binom{n}{r}$ is also commonly used for $_nC_r$ and is read as "n choose r".

Important Properties and Special Cases

• Choosing Zero Items: $_nC_0 = \frac{n!}{0!(n-0)!} = \frac{n!}{1 \cdot n!} = 1$. There is only one way to choose nothing (by selecting the empty set).
• Choosing All Items: $_nC_n = \frac{n!}{n!(n-n)!} = \frac{n!}{n!0!} = 1$. There is only one way to choose everything (by selecting the entire set).
• Symmetry Property: Choosing $r$ items to take is the same as choosing $n-r$ items to leave behind.

  $_nC_r = _nC_{n-r}$. For example, choosing 11 players from 15 ($_{15}C_{11}$) is the same as choosing 4 players to exclude ($_{15}C_4$). This property is very useful for simplifying calculations.

Answer:

Answer:

Important Results on Combinations

The formula for combinations, $_nC_r = \frac{n!}{r!(n-r)!}$, gives rise to several important identities and properties. These results are not just theoretical curiosities; they provide powerful shortcuts for solving complex counting problems and are fundamental to topics like the binomial theorem and probability.

Property 1: The Symmetry Property

This is one of the most frequently used properties of combinations. It states that the number of ways to choose $r$ objects from a set of $n$ is the same as the number of ways to choose $n-r$ objects from that set.

Combinatorial Proof (Intuitive Explanation):

Imagine you have $n$ distinct items. The act of choosing $r$ items to take with you is logically equivalent to choosing $n-r$ items to leave behind. For every group of $r$ items you select, you are simultaneously defining a group of $n-r$ items that you are not selecting. Therefore, the number of ways to perform these two actions must be the same.

Algebraic Proof:

We start with the right side of the equation, $_nC_{n-r}$, and show that it simplifies to the formula for $_nC_r$.

Simplify the second term in the denominator: $n-(n-r) = n-n+r = r$.

By the commutative property of multiplication, this is the same as the formula for $_nC_r$.

Answer:

Property 2: Pascal's Identity

This identity relates combinations of size $n$ to combinations of size $n+1$ and is the fundamental rule used to construct Pascal's Triangle.

Combinatorial Proof (Intuitive Explanation):

Suppose we want to form a committee of $r$ people from a group of $n+1$ people. The total number of ways to do this is $_{n+1}C_r$.

Now, let's consider one specific person in the group, say, "Person A". The committee we form will either include Person A or it will not. These are two mutually exclusive cases.

• Case 1: The committee includes Person A.

  Since Person A is already chosen for the committee, we only need to choose the remaining $r-1$ members from the remaining $n$ people. The number of ways to do this is $_nC_{r-1}$.

• Case 2: The committee does NOT include Person A.

  Since Person A is excluded, we must choose all $r$ members from the other $n$ people. The number of ways to do this is $_nC_r$.

By the Addition Principle, the total number of ways to form the committee is the sum of the ways in these two cases. Therefore, $_{n+1}C_r = _nC_r + _nC_{r-1}$.

Property 3: Sum of All Combinations

The sum of all combinations for a given $n$, from choosing 0 items up to choosing all $n$ items, is equal to $2^n$.

Combinatorial Proof (Intuitive Explanation):

Consider a set with $n$ distinct elements. The number of subsets of this set can be found by considering each element one by one. For each of the $n$ elements, we have two choices: either we include it in the subset, or we do not.

• For element 1: 2 choices (in or out)
• For element 2: 2 choices (in or out)
• ...
• For element n: 2 choices (in or out)

Alternatively, we can count the subsets by their size. The number of subsets of size 0 is $_nC_0$. The number of subsets of size 1 is $_nC_1$, and so on, up to the number of subsets of size $n$, which is $_nC_n$. Summing these up gives the total number of subsets. Therefore, the sum must equal $2^n$.

Answer:

Division into Groups

Beyond arranging or selecting objects, we sometimes need to solve problems that involve dividing a set of distinct objects into smaller subsets or groups. The method for counting the number of ways to do this depends crucially on whether the groups are considered distinguishable (e.g., labelled groups, groups assigned to different people) or indistinguishable (e.g., identical boxes, unnamed groups of the same size).

Case 1: Dividing $n$ Distinct Objects into $k$ Distinct Groups

Suppose we have $n$ distinct objects to be divided into $k$ groups that are distinguishable (e.g., a group for Person A, a group for Person B, etc.). Let the sizes of these groups be $n_1, n_2, \dots, n_k$, where $n_1 + n_2 + \dots + n_k = n$.

We can think of this as a sequence of selections:

1. First, choose $n_1$ objects for the first group from the $n$ available objects. This can be done in $_nC_{n_1}$ ways.
2. Next, from the remaining $n-n_1$ objects, choose $n_2$ objects for the second group. This can be done in $_{n-n_1}C_{n_2}$ ways.
3. Continue this process until all groups are formed.

By the Multiplication Principle, the total number of ways is the product of these combinations. This simplifies to the multinomial coefficient formula:

Case 2: Dividing $n$ Distinct Objects into Indistinguishable Groups

This case is more nuanced. It applies when the groups themselves have no labels or distinguishing features (e.g., dividing items into identical piles).

The key difference arises when some of the groups are of the same size. If we have $m$ indistinguishable groups of the same size $s$, the formula from Case 1 would overcount the arrangements because it treats the $m!$ ways of swapping these identical-sized groups as distinct. To correct this, we must divide by $m!$.

Rule of Thumb:

1. Start with the formula from Case 1: $\frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_k!}$.
2. Look at the group sizes ($n_1, n_2, \dots$).
3. If there are $m$ groups of the same size, divide the result by $m!$. If there are multiple sets of same-sized groups, divide by the factorial of the count for each set.

The general formula for dividing $n$ objects into $m_1$ indistinguishable groups of size $s_1$, $m_2$ indistinguishable groups of size $s_2$, etc., is:

Answer:

Answer:

Distribution of Identical Objects into Distinct Groups

This section deals with a type of counting problem where the objects being distributed are identical, unlike the problems in standard permutations and combinations where objects are distinct. We are interested in finding the number of ways to distribute $n$ identical items into $r$ distinct containers.

This type of problem is equivalent to finding the number of non-negative integer solutions to a linear equation.

The Stars and Bars Method

Consider the problem of finding the number of non-negative integer solutions to an equation of the form:

Here, $x_1, x_2, \dots, x_r$ represent the number of items in $r$ distinct bins, and $n$ is the total number of identical items to be distributed. The condition is that each bin can hold any number of items, including zero ($x_i \ge 0$).

We can visualize this problem using a technique called "Stars and Bars".

• Imagine the $n$ identical objects as $n$ "stars" ($\star$).
• To divide these stars into $r$ distinct groups, we need $r-1$ "bars" ($|$). The bars act as separators.

For example, to find the solutions for $x_1 + x_2 + x_3 = 5$ ($n=5, r=3$), we need $n=5$ stars and $r-1=2$ bars. An arrangement like:

$\star \star \star | \star | \star$

corresponds to the solution $x_1=3, x_2=1, x_3=1$. Another arrangement:

$| \star \star | \star \star \star$

corresponds to the solution $x_1=0, x_2=2, x_3=3$.

Each unique arrangement of these stars and bars gives a unique solution. The problem now is to find how many ways we can arrange $n$ stars and $r-1$ bars.

We have a total of $n + r - 1$ positions to fill. We just need to choose which $r-1$ of these positions will contain bars (the rest will automatically be stars). This is a combination problem.

The number of ways to choose $r-1$ positions for the bars from a total of $n+r-1$ positions is:

By the symmetry property of combinations, this is also equal to $_{n+r-1}C_n$.

Positive Integer Solutions (Each Group must have at least one object)

Sometimes, we require that each group must have at least one object. This corresponds to finding the number of positive integer solutions to the equation $x_1 + x_2 + \dots + x_r = n$, where $x_i \ge 1$.

To solve this, we can use a simple trick:

Step 1: First, place one object in each of the $r$ groups to satisfy the condition. This uses up $r$ of the $n$ objects.

Step 2: We are now left with $n - r$ identical objects to distribute among the $r$ groups, with no restrictions (i.e., each group can now receive zero or more additional objects).

This reduces the problem to the non-negative case we solved above. We just need to find the number of non-negative solutions for distributing $n' = n-r$ items into $r$ groups. Using the Stars and Bars formula with $n-r$ stars and $r-1$ bars:

Total positions = $(n-r) + (r-1) = n-1$.

Number of bars to place = $r-1$.

This formula is valid only if $n \ge r$. If $n < r$, it's impossible to place at least one object in each group, so the number of solutions is 0.

Answer:

Answer: